

	SIRURI 2-3-MONOTONE
       ---------------------

	Fie N un numar natural.
	Numim sir 2-3-monoton de lungime N un sir s1,s2,..,sN, format
din N elemente ale multimii {1,2,..,N} care verifica urmatoarele 2
relatii:

* s(i) < s(i+2), pt. orice i din {1,2,..,N-2}
* s(i) < s(i+3), pt. orice i din {1,2,..,N-3}


Cerinta: Scrieti un program care sa determine numarul de siruri
         2-3-monotone de lungime N.

Date de intrare:
	Fisierul de intrare SIR.IN contine un singur numar, lungimea N.

Date de iesire:
	Fisierul de iesire SIR.OUT contine pe prima linie ultimele 4
cifre din numarul de siruri 2-3-monotone de lungime N.


Restrictii si precizari:

* N numar natural, 1<=N<=50
* in cazul in care ultimele 4 cifre din numarul de siruri 2-3-monotone
  incep cu zerouri, acestea nu vor fi obligatoriu afisate

Exemple:

SIR.IN		SIR.OUT
2		4

SIR.IN		SIR.OUT
3		0009


Timp maxim de executie/test: 1 secunda